1. Field of the Invention
This invention relates to a method of and an apparatus for identifying an unknown system using an adaptive filter.
2. Description of the Related Art
Identification of an unknown system using an adaptive filter proceeds such that the same signal is inputted both to an unknown system to be identified and to an adaptive filter, and coefficients of the adaptive filter are updated using the identification error obtained by subtracting an output of the adaptive filter from the output of the unknown system. The identification error will hereinafter be referred to as an error signal. This identification of an unknown system using an adaptive filter can be applied, for example, to an echo canceler for removing echoes which may be produced at a two-line to four-line converting portion on a transmission line, an equalizer for removing intersymbol interference between codes which may take place in transmission lines, a noise canceler for removing noise which may leak into a sound inputting microphone, a howling canceler for removing howling which may be caused by acoustic coupling from a loudspeaker to a microphone, and various other apparatus. An exemplary common document regarding an adaptive filter is B. Widrow et al., "Adaptive Signal Processing", (Prentice-Hall, N.J., 1985) (hereinafter referred to as reference 1.) Here, operation of an adaptive filter is described taking a noise canceler as an example.
A noise canceler generally operates such that, using an adaptive filter having a transfer function approximated to an impulse response of a path from a noise source to a main input terminal, a noise replica corresponding to a noise component mixed into the main input terminal is produced to suppress the noise which is admitted into the main input terminal and gives a disturbance to a signal. In this instance, coefficients at taps of the adaptive filter are successively modified by taking the correlation between a difference signal obtained by subtraction of the noise replica from a mixed signal in which noise and an original signal are mixed and a reference noise available at a reference input terminal. As an exemplary algorithm for this coefficient modification of an adapive filter, that is, for convergence of a noise canceler, the LMS algorithm disclosed in reference 1 above and the learning identification method (LIM) disclosed in J. Nagumo et al., IEEE Transactions on Automatic Control, Vol. AC-12, No. 3, pp. 282-287 (1967) (hereinafter referred to as reference 2) are known.
FIG. 1 is a block diagram showing the construction of an example of a conventional noise canceler. Referring to FIG. 1, a mixed signal in which a signal detected at main input terminal 1 and noise are mixed is supplied to subtracter 4. A reference noise signal detected at reference input terminal 2 is supplied to adaptive filter 3. A noise replica generated by adaptive filter 3 is subtracted from the mixed signal at subtracter 4. Consequently, the noise components in the mixed signal are cancelled and a signal wherein the noise is removed is supplied to output terminal 6. Output of subtracter 4 is supplied also to multiplier 5, at which it is multiplied by 2.alpha.. Output of multiplier 5 is used for updating of the coefficients of adaptive filter 3. Here, .alpha. is a constant and called a step size. Now, if a signal is represented by s.sub.k (k is an index representative of time), reference noise by n.sub.k, noise to be erased by v.sub.k, and additional noise that signal s.sub.k undergoes by .delta..sub.k, then signal w.sub.k to be supplied from input terminal 1 to subtracter 4 is given by: EQU w.sub.k =s.sub.k +v.sub.k +.delta..sub.k ( 1)
The object of the noise canceler is to produce replica u.sub.k of noise component v.sub.k defined by equation (1) to cancel noise. By producing noise replica u.sub.k adaptively using a closed loop circuit consisting of adaptive filter 3, subtracter 4 and multiplier 5 shown in FIG. 1, difference signal d.sub.k given by the following equation can be obtained as an output signal of subtracter 4: EQU d.sub.k =s.sub.k +v.sub.k -u.sub.k ( 2)
Since it is considered that generally .delta..sub.k is small enough compared with s.sub.k, .delta..sub.k is ignored here. (v.sub.k -u.sub.k) in equation (2) above is called residual noise, and from the point of view of system identification, this residual noise is equal to an error signal. If the LMS algorithm is assumed, then m-th coefficient c.sub.m,k+1 of adaptive filter 3 is updated in accordance with the following equation: EQU c.sub.m,k+1 =c.sub.m,k +2.alpha..multidot.d.sub.k .multidot.n.sub.m,k( 3)
If equation (3) is represented in a matrix form for all N coefficients, then EQU c.sub.k+1 =c.sub.k +2.alpha..multidot.d.sub.k .multidot.n.sub.k( 4)
where c.sub.k and n.sub.k are given by the following equations, respectively: EQU c.sub.k =[c.sub.0,k c.sub.1,k . . . c.sub.N-1,k ].sup.T ( 5) EQU n.sub.k =[n.sub.k n.sub.k-1 . . . n.sub.k-N+1 ].sup.T ( 6)
where [.].sup.T represents transposition of the matrix. On the other hand, according to LIM, updating of coefficients are performed in accordance with following equation (7) in place of equation (4): EQU c.sub.k+1 =c.sub.k +(2.mu./N.delta..sub.n.sup.2).multidot.d.sub.k .multidot.n.sub.k ( 7)
where .mu. is a step size in LIM, and .sigma..sub.n.sup.2 is an average power inputted to adaptive filter 3. Parameter .sigma..sub.n.sup.2 is used so that the value of step size .mu. may increase in inverse proportion to the average power in order to assure stabilized convergence. Various methods are available to calculate .sigma..sub.n.sup.2, and .sigma..sub.n.sup.2 can be calculated, for example, in accordance with following equation (8): ##EQU1##
Step sizes .alpha. and .mu. in equations (4) and (7) define the rate of convergence of the adaptive filter and the level of residual noise after convergence. In the case of LMS, as the value of .alpha. increases, the convergence occurs more rapidly, but the residual noise level increases. On the contrary, in order to attain a sufficiently low residual noise level, .alpha. having a corresponding low value must necessarily be adopted, which results in deterioration in convergence rate. This similarly applies to step size .mu. in LIM.
In order to satisfy the contradictory requirements for the step sizes and the residual noise, an algorithm wherein the step size is variable has been proposed and is disclosed in Proceeding of International Conference on Acoustics, Speech and Signal Processing, pp. 1385-1388, 1990 (hereinafter referred to as reference 3.) The algorithm will be hereinafter referred to as SGA-GAS (Stochastic Gradient Adaptive Filters with Gradient Adaptive Step Size).
SGA-GAS uses .alpha..sub.k in place of step size .alpha. of the LMS algorithm of equation (4). Parameter .alpha..sub.k is defined by equation (9) below as a value which increases in proportion to the negative gradient of power d.sub.k.sup.2 of difference signal .alpha..sub.k : ##EQU2## wherein .rho. is a positive constant and normally a very small value is used therefor. Equation (9) can be rewritten, using noise n.sub.k, as: EQU .alpha..sub.k =.alpha..sub.k-1 +.rho.d.sub.k d.sub.k-1 n.sub.k-1.sup.T n.sub.k ( 10)
Further, .alpha..sub.k must satisfy the following condition: ##EQU3## where {.}.sup.T is transposition of the matrix, tr{.} a trace of the matrix, and R an autocorrelation matrix of noise n.sub.k.
FIG. 2 is a block diagram showing an example of construction of a noise canceler which employs the SGA-GAS algorithm. While the step size is fixed in the noise canceler shown in FIG. 1, it is variable in the noise canceler shown in FIG. 2. In particular, step size .alpha..sub.k represented by equation (10) is calculated by step size controller 8 and then limited by limiter 9, whereafter it is supplied to adaptive filter 3 via multiplier 5. An example of construction of step size controller 8 is shown in a block diagram of FIG. 3.
Referring to FIG. 3, step size controller 8 has two input terminals 90 and 93 and single output terminal 100 and includes correlation calculating circuit 94, three multipliers 92, 96 and 97, two delay elements 91 and 99 and adder 98. Difference signal d.sub.k is supplied to first input terminal 90 while reference noise n.sub.k is supplied to second input terminal 93. Step size .alpha..sub.k which is an output of step size controller 8 is supplied from output terminal 100 to limiter 9 of FIG. 2. Signal d.sub.k supplied to first input terminal 90 is delayed by one sample period by first delay element 91 to make d.sub.k-1 and is supplied to first multiplier 92. Signal d.sub.k is also supplied to first multiplier 92, and d.sub.k .multidot.d.sub.k-1 which is an output of first multiplier 92 is transmitted to second multiplier 96:
Reference noise n.sub.k supplied to second input terminal 93 is transmitted to correlation calculating circuit 94. Correlation C.sub.k, which is defined by the following equation, is calculated by correlation calculating circuit 94 and transmitted to second multiplier 96. EQU C.sub.k =n.sub.k-1.sup.T n.sub.k ( 12)
Correlation C.sub.k is multiplied by d.sub.k .multidot.d.sub.k-1 by second multiplier 96 and is further multiplied by .rho. by third multiplier 97, whereafter it is transmitted as .rho..multidot.d.sub.k .multidot.d.sub.k-1 .multidot.n.sub.k-1.sup.T .multidot.n.sub.k to adder 98. At adder 98, the signal from third multiplier 97 is added to the signal which is an output of second delay element 99 and was obtained one sample period earlier, and the sum signal is transmitted to output terminal 100. Accordingly, signal .alpha..sub.k transmitted to output terminal 100 is given by .alpha..sub.k-1 +.rho.d.sub.k d.sub.k-1 n.sub.k-1.sup.T n.sub.k, which coincides with equation (10) above.
FIG. 4 is a block diagram showing construction of correlation calculating circuit 94. Correlation calculating circuit 94 includes N-input adder 123, N delay elements 121.sub.1 to 121.sub.N and N multipliers 122.sub.1 to 122.sub.N. Delay elements 121.sub.1 to 121.sub.N are connected in series and form a tapped delay line, to which multipliers 122.sub.1 to 122.sub.N are connected respectively. Input terminal 120 of correlation calculating circuit 94 corresponds to second input terminal 93 in FIG. 3 and receives n.sub.k thereat. Signal n.sub.k is supplied to the delay line with taps and first multiplier 122.sub.1. For 2.ltoreq.i.ltoreq.N, outputs of (i-1)-th and i-th delay elements 121.sub.i-1 and 121.sub.i are supplied to i-th multiplier 122.sub.i. Accordingly, (n.sub.k, n.sub.k-1), (n.sub.k-1, n.sub.k-2), . . . , (n.sub.k-N+1, n.sub.k-N) are inputted to multipliers 122.sub.1, 122.sub.2, . . . , 122.sub.N, respectively, and outputs of the multipliers are given by n.sub.k n.sub.k-1, n.sub.k-1 n.sub.k-2, . . . , n.sub.k-N+1 n.sub.k-N.
Outputs of multipliers 122.sub.1 to 122.sub.N are all supplied to adder 123, and a value given by ##EQU4## is outputted from adder 123. Output n.sub.k-1.sup.T .multidot.n.sub.k is transmitted as correlation C.sub.k to output terminal 124 of correlation calculating circuit 94.
Referring now to FIG. 5, limiter 9 includes 2-input minimum value circuit 22 and 2-input maximum value circuit 21. Step size .alpha..sub.k is supplied to minimum value circuit 22 from step size controller 8 by way of input terminal 23. Th.sub.H, which is a threshold value for a maximum value, is supplied to the other input terminal of minimum value circuit 22, and a smaller value of .alpha..sub.k and Th.sub.H is supplied as a minimum value from minimum value circuit 22 to maximum value circuit 21. Th.sub.L, which is a threshold value for a minimum value, is supplied to the other input terminal of maximum value circuit 21, and a greater value of the output of minimum value circuit 22 and Th.sub.L is supplied as a maximum value from maximum value circuit 21 to output terminal 20. In other words, step size .alpha..sub.k supplied to input terminal 23 is limited, at upper and lower limits thereof, with minimum value Th.sub.L and maximum value Th.sub.H, respectively, so that it is outputted as .alpha..sub.k given by the following equation: ##EQU5## Here, if Th.sub.L =0 and Th.sub.H =2/(3.multidot.tr{R}), then a value equivalent to a value obtained by execution of equation (11) is outputted from limiter 9.
Maximum value circuit 21 and minimum value circuit 22 can each be realized by a combination of selector 31 and comparator 32 as shown in FIG. 6. Minimum value circuit 21 will be described first. The two input terminals of minimum value circuit 22 in FIG. 5 correspond to two input terminals 33 and 34, respectively, of FIG. 6. Signals supplied to input terminals 33 and 34 are transmitted simultaneously to both selector 31 and comparator 32. Comparator 32 compares the two input signals with each other and generates a controlling signal such that a smaller signal is selected by selector 31. The controlling signal is transmitted to selector 31, and the signal from input terminal 33 or 34 selected by selector 31 is transmitted as a minimum value to output terminal 30. On the other hand, in the case of maximum value circuit 21, comparator 32 generates a controlling signal such that selector 31 selects the greater signal of the two input signals supplied thereto. Selector 31 then supplies the signal selected in accordance with the controlling signal as a maximum value to output terminal 30.
Identification of an unknown system based upon the SGA-GAS algorithm has been described so far by way of an example of a noise canceler. Here, in an ideal case wherein d.sub.k =v.sub.k -u.sub.k is met with difference signal d.sub.k, the negative gradient of power d.sub.k.sup.2 of difference signal d.sub.k coincides with a system identification error, and consequently, d.sub.k.sup.2 can be used for step size control. However, in an actual noise canceler, d.sub.k is given by d.sub.k =s.sub.k +v.sub.k -u.sub.k as represented in equation (2) and accordingly is influenced by signal s.sub.k. Therefore, a correct gradient of d.sub.k.sup.2 cannot be obtained, and the step size cannot be controlled correctly. In some other apparatus described above other than a noise canceler, even when s.sub.k =0, when additional noise .delta..sub.k in equation (1) cannot be ignored, difference signal d.sub.k is given by EQU d.sub.k =v.sub.k -u.sub.k +.delta..sub.k ( 15)
and consequently, .delta..sub.k makes an obstruction to error signal v.sub.k -u.sub.k similar to s.sub.k. The presence of parameter .delta..sub.k or s.sub.k will result in elongation in converging time or an increase in final misadjustment after convergence.